原题地址：Pow(x, n)
实现 $pow(x, n)$ ，即计算 x 的 n 次幂函数。
示例 1:
输入: 2.00000, 10
输出: 1024.00000
示例 2:
输入: 2.10000, 3
输出: 9.26100
示例 3:
输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25
说明:
- -100.0 < x < 100.0
- n 是 32 位有符号整数，其数值范围是 [$-2^{31}$, $2^{31}-1$] 。
连乘
按幂的计算规则，将x连乘n次即可，注意处理n为负的情况：
/**
* @param {number} x
* @param {number} n
* @return {number}
*/
const myPow1 = function(x, n) {
// x^n = (1/x)^(-n)，统一将n转为正数计算
if (n < 0) {
x = 1 / x;
n = -n;
}
// 依次累乘即可
let result = 1;
for (let i = 0; i < n; i ++) {
result *= x;
}
return result;
};
测试：
let start = new Date();
const test = myPow1;
console.log(test(2.00000, 10)); // 1024
console.log(test(2.10000, 3)); // 9.261000000000001
console.log(test(2.00000, -2)); // 0.25
console.log(new Date().getTime() - start.getTime()); // 8
时间复杂度： 连乘n次，时间复杂度为$O(N)$，其中N为绝对值，当N过大时，会超时
空间复杂度： 空间复杂度为$O(1)$
二分优化
利用$x^{2i}=x^i \times x^i$，我们可以将连乘优化，时间复杂度降为$O(logN)$：
/**
* 递归计算幂
* @param x 乘数
* @param n 幂
* @returns {number} pow(x,n)
*/
const fastPow = (x, n) => {
// 任何数的0次方都等于1
if (n === 0) {
return 1;
}
// 计算 x^(n/2)
let fast = fastPow(x, Math.floor(n / 2));
if ( n % 2 === 0) {
// 如果n为偶数，那么x^n = x^(n/2) * x^(n/2)
return fast * fast;
} else {
// 如果x为奇数，额外乘上x即可
return fast * fast * x;
}
};
/**
* @param {number} x
* @param {number} n
* @return {number}
*/
const myPow2 = function(x, n) {
// x^n = (1/x)^(-n)，统一将n转为正数计算
if (n < 0) {
x = 1 / x;
n = -n;
}
return fastPow(x, n);
};
测试：
let start = new Date();
const test = myPow1;
console.log(test(2.00000, 10)); // 1024
console.log(test(2.10000, 3)); // 9.261000000000001
console.log(test(2.00000, -2)); // 0.25
console.log(new Date().getTime() - start.getTime()); // 7
时间复杂度： 时间复杂度为$O(logN)$
空间复杂度： 每一次计算结果都需要保存，直到得出最终结果，空间复杂度为$O(logN)$
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Aug 13,2019